package com.kongge.algorithm.demo;

/**
 * 斐波那契数列
 * @author gaoshiqi
 *
 */
public class Fibonacci implements IAlgorithm {

	public void execute() {
		int number = 40;
		long traveseStartTime = System.currentTimeMillis();
		System.out.println("Fibonacci递归 " + number + ":" + calTraveseFibonacci(number));
		long traveseEndTime = System.currentTimeMillis();
		
		System.out.println("\nFibonacci循环 " + number +":" + calLoopFibonacci(number));
		long loopEndTime = System.currentTimeMillis();
		
		long timeBetween = (traveseEndTime - traveseStartTime) - (loopEndTime - traveseEndTime);
		System.out.println("\n循环 " + number + " 次，循环比递归快 " + timeBetween + "ms");
	}
	
	/**
	 * 递归调用
	 * @param number
	 * @return
	 */
	private int calTraveseFibonacci(int number) {
		if (number <= 0) {
			return 0;
		}
		if (number == 1) {
			return 1;
		}
		return calTraveseFibonacci(number - 2) + calTraveseFibonacci(number - 1);
	}
	
	/**
	 * 循环调用
	 * @param number
	 * @return
	 */
	private int calLoopFibonacci(int number) {
		if (number <= 0) {
			return 0;
		}
		if (number == 1) {
			return 1;
		}
		int result = 0;
		int firstNum = 0;
		int secondNum = 1;
		for (int i = 2; i <= number; i++) {
			result = firstNum + secondNum;
			firstNum = secondNum;
			secondNum = result;
		}
		return result;
	}
	

}
